package com.lzhsite.leetcode.algoritom.practise.dynamicProgramming;

//给定一个无序的整数数组，找到其中最长上升子序列的长度。
//
//示例:
//
//输入: [10,9,2,5,3,7,101,18]
//输出: 4 
//解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
//说明:
//可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
//你算法的时间复杂度应该为 O(n2) 。
//进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

public class LeetCode300最长上升子序列 {

	// 基于二分法
	private static int getMaxIncrSubStr2(Integer arr[]){
		
		//top[]数组用来记录arr[i]所放的堆叠
		//如top[0]=arr[3]表示arr[3]放在第一个堆叠
		//如top[1]=arr[2]表示arr[2]放在第一二个堆叠
		int [] top = new int[arr.length];
		
		int left=0,right=0;
		int mid = 0;

		//堆叠数
		int pfiles = 0;
		for (int i = 0; i < arr.length; i++) {
			
			right = pfiles;
			//无法搜索到目标值,退出去循环后一定left==right
			while (left < right) {
				 mid = (left+right)/2;
				 if(top[mid] < arr[i]){
					 left = mid+1;   //mid+1赋给left是因为(left+right)/2是向下取整,需要补偿left
				 }else if(top[mid] > arr[i]){
					 right = mid;
				 }else{
					 right = mid;
					 break;
				 }
			}
		
			
			//放第一张牌或找不到目标牌叠且大于最后一个堆叠的top值，创建一个堆叠数
			if(pfiles==0 || left == mid+1){
				pfiles++;
				top[pfiles-1] = arr[i];
			}else{
				//找到目标牌叠或找不到目标牌叠且小于第一个堆叠的top值,
				top[right] = arr[i];
			}

		}
		
		System.out.print(pfiles);
		return pfiles;
	}

	// 动态规划
	private static int getMaxIncrSubStr(Integer arr[]) {

		// dp[i]表示以arr[i]结尾,并且arr[i]是递增子序列最后一个的元素最大递增子序列长度，
		int dp[] = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			dp[i] = 1;
		}
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < i; j++) {
				// 倒数第二个a[j]小于a[i]时才计算dp[i]
				// dp[i]是以于a[j]为倒数第二个元素的最大递增子序列里的最大值
				if (arr[i] > arr[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}

			}
		}
		// max用来标记最大递增子序列的长度,还需要一个副本max1来记录max的值
		int max = -1, max1 = -1;
		// index用来记录递增子序列的最后一值在arr中的下标
		int index = 0;
		for (int i = 0; i < dp.length; i++) {
			if (max < dp[i]) {
				index = i;
			}
			max = Math.max(max, dp[i]);
			max1 = max;

		}

		
		//下面是寻找具体最大递增子序列的逻辑可以不看值当练手
		int[] subStArr = new int[max];
		// 递增子序列的最后一个值
		subStArr[max - 1] = arr[index];
		max1--;
		for (int i = index - 2; i > 0; i--) {

			// 符合dp[i+1] - dp[i]== 1 && arr[i] < subStArr[max1]的值才能放入递增子序列
			// 就是连续的dp值要差1,上一个元素一定要比后面的元素小
			if (dp[i + 1] - dp[i] == 1 && arr[i] < subStArr[max1]) {
				subStArr[max1 - 1] = arr[i];
				max1--;
			}
		}

		for (int i = 0; i < subStArr.length; i++) {
			System.out.print(subStArr[i] + " ");
		}

		return max;
	}

	public static void main(String[] args) {
		Integer[] arr = { 10, 9, 2, 5, 3, 7, 101, 18 };
		getMaxIncrSubStr2(arr);
	}
}
